package ArrayList;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-05-21
 * Time: 12:09
 */

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

//class Solution1 {
//    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
//        TreeNode root = null;
//        //1.处理为不为空的情况
//        //如果一颗二叉树为空，则另外一个节点就是root节点
//        if(root1==null&&root2!=null){
//            root = root2;
//        }
//        if(root2==null&&root1!=null){
//            root = root1;
//        }
//        //两个都为空则返回null
//        if(root1==null&&root2==null){
//            return null;
//        }
//        //2.处理正常情况--->此时两者都不为空
//        if(root1!=null&&root2!=null){
//            if(root==null){
//                root = new TreeNode(root1.val+root2.val);
//            }else {
//                root.val = root1.val+root2.val;
//            }
//            root.left = mergeTrees(root1.left,root2.left);
//            root.right = mergeTrees(root1.right,root2.right);
//        }
//        return root;
//    }
//}

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int max = 0;
        while(!queue.isEmpty()){
            int sz = queue.size();
            max = Math.max(max,sz);
            TreeNode cur =queue.poll();
            while(sz!=0){
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                sz--;
            }
        }
        int tmp = (int)(Math.pow(2,max-1));
        return tmp;
    }
}


public class TestArrayList {
    public static void main(String[] args) {
        Solution solution = new Solution();
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(5);
        TreeNode node5 = new TreeNode(3);
        TreeNode node6 = new TreeNode(9);
        node1.left =node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.right = node6;
        solution.widthOfBinaryTree(node1);
    }

}
